﻿using System;


public class LinkListExample
{
    // 头插法，创建单链表(屏幕输入链表元素，-1结束)
    SingleLinkedList<int> CreateIListHead()
    {
        int d;
        SingleLinkedList<int> L = new SingleLinkedList<int>();
        d = Int32.Parse(Console.ReadLine());
        while (d != -1)
        {
            Node<int> p = new Node<int>(d);
            p.Next = L.Head;
            L.Head = p;

            d = Int32.Parse(Console.ReadLine());
        }
        return L;
    }

    // 尾插法 R作为尾结点
    SingleLinkedList<int> CreateListTail()
    {
        Node<int> R = new Node<int>();
        int d;
        SingleLinkedList<int> L = new SingleLinkedList<int>();
        R = L.Head;
        d = Int32.Parse(Console.ReadLine());
        while (d != -1)
        {
            Node<int> p = new Node<int>(d);
            if (L.Head == null)
            {
                L.Head = p;
            }
            else
            {
                R.Next = p;
            }
            R = p;
            d = Int32.Parse(Console.ReadLine());
        }

        if (R != null)
        {
            R.Next = null;
        }
        return L;
    }

    // 单链表倒置
    public static void ReversLinkList(SingleLinkedList<int> L)
    {
        Node<int> p = L.Head;
        Node<int> q = new Node<int>();
        Node<int> tmp = null;
        L.Head = null;
        while (p != null)
        {
            q = p;
            p = p.Next;
            q.Next = tmp;
            tmp = q;
        }
        L.Head = q;
    }

    // 将两个单链表（有序）的数据合并到大的单链表,尾插
    public SingleLinkedList<int> MergeTail(SingleLinkedList<int> Ha, SingleLinkedList<int> Hb)
    {
        SingleLinkedList<int> Hc = new SingleLinkedList<int>();
        Node<int> p = Ha.Head;
        Node<int> q = Hb.Head;
        Node<int> s = new Node<int>();
        while (p != null && q != null)
        {
            if (p.Data < q.Data)
            {
                s = p;
                p = p.Next;
            }
            else
            {
                s = q;
                q = q.Next;
            }
            Hc.Append(s.Data);
        }

        if (p == null)
        {
            p = q;
        }

        while (p != null)
        {
            s = p;
            p = p.Next;
            Hc.Append(s.Data);
        }
        return Hc;
    }

    //  将两个单链表（有序）的数据合并到大的单链表,头插(相对尾插法，性能更好)
    public SingleLinkedList<int> MergeHead(SingleLinkedList<int> Ha, SingleLinkedList<int> Hb)
    {
        SingleLinkedList<int> Hc = new SingleLinkedList<int>();
        Node<int> p = Ha.Head;
        Node<int> q = Hb.Head;
        Node<int> s = new Node<int>();
        while (p != null && q != null)
        {
            if (p.Data < q.Data)
            {
                s = p;
                p = p.Next;
            }
            else
            {
                s = q;
                q = q.Next;
            }
            s.Next = Hc.Head;
            Hc.Head = s;
        }

        if (p == null)
        {
            p = q;
        }

        while (p != null)
        {
            s = p;
            p = p.Next;
            s.Next = Hc.Head;
            Hc.Head = s;
        }
        return Hc;
    }

    // 去重
    public SingleLinkedList<int> Purge(SingleLinkedList<int> Ha)
    {
        SingleLinkedList<int> Hb = new SingleLinkedList<int>();
        Node<int> p = Ha.Head;
        Node<int> q = new Node<int>();
        Node<int> s = new Node<int>();

        s = p;
        p = p.Next;
        s.Next = null;
        while (p != null)
        {
            s = p;
            p = p.Next;
            q = Hb.Head;
            while (q != null && q.Data != s.Data)
            {
                q = q.Next;
            }

            if (q == null)
            {
                s.Next = Hb.Head;
                Hb.Head = s;
            }
        }
        return Hb;
    }

    /// <summary>
    /// 回文字符串判断
    /// </summary>
    /// <param name="str"></param>
    /// <returns></returns>
    public bool IsPalindrome(string str)
    {
        char[] arr = str.ToCharArray();
        SingleLinkedList<char> L = new SingleLinkedList<char>();
        for (int i = 0; i < arr.Length; i++)
        {
            L.Append(arr[i]);
        }

        if (L.Head.Next == null)
        {
            Console.WriteLine("只有一个元素");
            return true;
        }

        // 快慢指针
        Node<char> quick = L.Head;
        Node<char> slow = L.Head;
        while (slow.Next != null && quick.Next != null && quick.Next.Next != null)
        {
            slow = slow.Next;
            quick = quick.Next.Next;
        }
        Console.WriteLine("中间结点 " + slow.Data);

        Node<char> leftLink = null;
        Node<char> rightLink = null;
        if (quick.Next == null)
        {
            Console.WriteLine("开始执行奇数结点的回文判断");
            // slow 是中间结点，且结点数量为奇数
            rightLink = slow.Next;
            leftLink = L.Reverse(slow);
            Console.WriteLine("左边第一个结点" + leftLink.Data);
            Console.WriteLine("右边第一个结点" + rightLink.Data);
        }
        else
        {
            Console.WriteLine("开始执行偶数结点的回文判断");
            // 结点数为偶数
            rightLink = slow.Next;
            leftLink = L.Reverse(slow.Next);
        }

        while (leftLink != null && rightLink != null)
        {
            if (leftLink.Data == rightLink.Data)
            {
                leftLink = leftLink.Next;
                rightLink = rightLink.Next;
                continue;
            }
            else
            {
                return false;
            }

        }
        return true;
    }
}
